package com.cdy.demo.algorithm;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class Leetcode605 {

	public static void main(String[] args) {
		Leetcode605 Leetcode5 = new Leetcode605();
		System.out.println(Leetcode5.canPlaceFlowers(new int[]{1,0,0,0,1},1));
		System.out.println(Leetcode5.canPlaceFlowers(new int[]{1,0,0,0,1},2));

		System.out.println(Leetcode5.canPlaceFlowers(new int[]{1,0,0,0,1},2));
	}


	/**
	 * 插花
	 * @param flowerbed
	 * @param n
	 * @return
	 */
	boolean canPlaceFlowers(int[] flowerbed, int n) {
		if (n == 0) {
			return true;
		}
		if (flowerbed.length == 0) {
			return false;
		}
		for (int i = 0; i < flowerbed.length; i++) {
			if (flowerbed[i] == 0 && (i == flowerbed.length - 1 || flowerbed[i+1] == 0) && (i <= 0 || flowerbed[i - 1] == 0)) {
				n--;
				flowerbed[i] = 1;
			}
			if (n == 0) {
				return true;
			}
		}

		return false;
	}


	/**
	 * 1579 避免重复字母的最小删除成本
	 * @param s
	 * @param cost
	 * @return
	 */
	public int minCost(String s, int[] cost) {
		int i = 0, len = s.length();
		int ret = 0;
		while (i < len) {
			char ch = s.charAt(i);
			int maxValue = 0;
			int sum = 0;

			while (i < len && s.charAt(i) == ch) {
				maxValue = Math.max(maxValue, cost[i]);
				sum += cost[i];
				i++;
			}
			ret += (sum - maxValue);
		}
		return ret;
	}

}
